/*
 * @lc app=leetcode.cn id=LCP 33 lang=golang
 * @lcpr version=30119
 *
 * [LCP 33] 蓄水
 */

// @lcpr-template-start
package main

import (
	"container/heap"
	"math"
)

func main() {
	bucket := []int{0}
	vat := []int{1}
	storeWater(bucket, vat)
}

// @lcpr-template-end
// @lc code=start

type Node struct {
	Bucket int
	Vat    int
}

type MaxHeap []Node

func (h MaxHeap) Len() int { return len(h) }
func (h MaxHeap) Less(i, j int) bool {
	return math.Ceil(float64(h[i].Vat)/float64(h[i].Bucket)) > math.Ceil(float64(h[j].Vat)/float64(h[j].Bucket))
}
func (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) {
	*h = append(*h, x.(Node))
}
func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func storeWater(bucket []int, vat []int) int {
	pq := &MaxHeap{}
	ans := 0

	for i := 0; i < len(bucket); i++ {
		if vat[i] == 0 {
			continue
		}
		if bucket[i] == 0 {
			bucket[i]++
			ans++
		}
		heap.Push(pq, Node{bucket[i], vat[i]})
	}
	for pq.Len() > 0 {
		node := heap.Pop(pq).(Node)

		oldOps := math.Ceil(float64(node.Vat) / float64(node.Bucket))
		newOps := math.Ceil(float64(node.Vat) / float64(node.Bucket+1))
		if newOps+1 >= oldOps {
			heap.Push(pq, Node{node.Bucket, node.Vat})
			break
		}
		heap.Push(pq, Node{node.Bucket + 1, node.Vat})
		ans++
	}
	if len(*pq) == 0 {
		return ans
	}
	node := heap.Pop(pq).(Node)
	return ans + int(math.Ceil(float64(node.Vat)/float64(node.Bucket)))
}

// @lc code=end

/*
// @lcpr case=start
// [1,3]\n[6,8]`>\n
// @lcpr case=end

// @lcpr case=start
// [9,0,1]\n[0,2,2]`>\n
// @lcpr case=end

*/
